package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname ShellSort
 * @Project Data-structure-and-algorithm
 * @Description 希尔排序代码实现：移位法 效率更高
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键询越来越多，
 * 当增量减至1时，整个文件恰被分成一组，算法便终止
 * @Author wpcheng
 * @Create 2021-08-06-8:56
 * @Version 1.0
 */
public class DisplacementShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
    }

    public static void shellSort(int[] arr) {

        //根据下面的逐步分析，使用循环处理
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while(j-gap >= 0 && temp < arr[j-gap]){
                        arr[j] = arr[j-gap];
                        j-=gap;
                }
                   arr[j] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }


}

}
